package 力扣.树.后序遍历;

public class 验证二叉搜索树98 {
    class Node {
        public Long min = Long.MAX_VALUE;
        public Long max = Long.MIN_VALUE;
        public Node() {}
        public Node(Long l, Long r) {
            min = l;
            max = r;
        }
    }

    private boolean ans = true;
    private Node emptyRange = new Node();

    private Node postOrder(TreeNode root) {
        // 如果是空树，或者已经判断不是一棵二叉搜索树了
        // 那么就不需要再继续遍历了。
        if (root == null || !ans) {
            return emptyRange;
        }
        Node l = postOrder(root.left);
        Node r = postOrder(root.right);

        if (!(l.max < root.val && root.val < r.min)) {
            ans = false;
            // 当不符合的时候，返回任意区间都是可以的
            return emptyRange;
        }

        // 需要取左子树最小值与当前结点的最小值。
        // 需要取右子树最大值与当前结点的最大值
        return new Node(Math.min(l.min, root.val), Math.max(r.max, root.val));
    }

    public boolean isValidBST(TreeNode root) {
        ans = true;
        postOrder(root);
        return ans;
    }
}
